using System;
using System.IO;
// Zur Arbeit mit Datei
using System.Collections.Generic;
// Grundlegende Datenstrukturen
namespace GraphSpace
{
	public class Graph
	{
		// Liste der Knoten
		protected List<Knoten> v;
		// gerichtete Kanten :: Zugriff Start-Knoten ID -> Zugriff Ziel-Knoten ID -> Kante
		private Dictionary<int, List<Kante>> a;
		// gerichtete Rückwärts Kanten :: Zugriff Start-Knoten ID -> Zugriff Ziel-Knoten ID -> Kante
		private Dictionary<int, List<Kante>> ar;

		protected int m;
		
		public Graph ()
		{
			m = 0;
			v = new List<Knoten> ();
			a = new Dictionary<int, List<Kante>> ();
			ar = new Dictionary<int, List<Kante>> ();
		}

		public int bestimmeMaxKantengewicht()
		{
			int max = 0;
			for(int i=0; i< v.Count;i++)
				foreach(Kante kante in A[i])
				{
					if((Int32)(kante.Gewicht) > max)
						max = (Int32)(kante.Gewicht);
				}
			return max;
		}
		
		/// <summary>Methode zum Einfügen eines neuen Knotens</summary>
		/// <returns>false, wenn Knoten bereits im Graphen vorhanden ist</returns>
		/// <param name="id">ID des einzufügenden Knotens</param>
		/// <param name="daten">Daten am Knoten</param>
		public virtual bool neuerKnoten (int id)
		{
			if(v.Count == id)
			{
				v.Add(new Knoten(id, 0, 0));
				// Adjazensliste fuer Knoten anlegen (ungerichtet)
				a.Add (id, new List<Kante> ());
				ar.Add (id, new List<Kante> ());
				return true;
			}
			// Knoten-Id ist nicht die aktuell in Liste einzufügende
			return true;
		}
		
		public virtual bool neuerKnoten (Knoten knoten)
		{
			if(v.Count == knoten.id)
			{
				v.Add(knoten);
				// Adjazensliste fuer Knoten anlegen (ungerichtet)
				a.Add (knoten.id, new List<Kante> ());
				ar.Add (knoten.id, new List<Kante> ());
				return true;
			}
			// Knoten-Id ist nicht die aktuell in Liste einzufügende
			return true;
		}

		/// <summary>Methode zum EInfuegen einer neuen Kante (auch parallel).</summary>
		/// <param name="von">ID des Startknotens</param>
		/// <param name="nach">ID des Zielknotens</param>
		/// <param name="gewicht">Kantengewicht</param>
		/// <returns>false, wenn einer der beiden Knoten nicht im Graphen vorhanden</returns>
		public virtual bool neueKante (int von, int nach, double gewicht)
		{		
			if (v.Count > von && v.Count > nach) 
			{
				Knoten knoten1 = v[von];
				Knoten knoten2 = v[nach];
			
				Kante hin = new Kante(knoten1, knoten2, gewicht);
				Kante rueck = new Kante(knoten2, knoten1, gewicht);
				
				// ungerichtet
				a[von].Add (hin);
				// Kante in Adjazensliste des Start-Knotens einfuegen
				ar[nach].Add (rueck);
				// Kante in Adjazensliste des Start-Knotens einfuegen (2. Richtung)
				// gerichtet
				m++;
				return true;
			}
			
			return false;
			// Knoten war noch nicht vorhanden
		}
		
		/// <summary>Abfrage, ob Knoten mit ID im Graphen vorhanden ist</summary>
		/// <param name="id">ID des Knotens</param>
		/// <returns>true, wenn Knoten im Graphen vorhanden</returns>
		public bool enthaeltKnoten (int id)
		{
			if(v.Count>id)
				return true;
			else
				return false;
		}

		public Knoten holeKnoten (int id)
		{
			return v[id];
		}

		/// <summary>Ruft die reset-Methode auf allen Knoten des Graphen auf 
		/// und setzt damit deren Attribute fuer Algorithmen zurueck</summary>
		public void resetV ()
		{
			foreach (Knoten w in v)
				w.reset ();
		}

		
		/// <summary>Methode zum Einlesen eines Graphen aus Datei, wobei die Knoten 
		/// Koordinaten besitzen und die Kantengewichte die euklidischen Distanzen sind. 
		/// Dabei werden alle zuvor gesetzten Knoten und Kanten entfernt</summary>
		/// <param name="pfad">Pfad zur Datei</param>
		/// <returns>false, wenn Datei nicht eingelesen werden konnte</returns>
		public virtual bool ladeEuklidGraph (string pfad)
		{
			string zeile = "";
			if (File.Exists (pfad)) {
				// Graph leeren				
				v = new List<Knoten> ();
				a = new Dictionary<int, List<Kante>> ();
				ar = new Dictionary<int, List<Kante>> ();
				
				// Datei einlesen
				StreamReader reader = new StreamReader (pfad, System.Text.Encoding.Default);
				// erste Zeile mit Basiswerten einlesen
				int datei_n, datei_m;
				zeile = reader.ReadLine ();
				if(zeile.Split (' ').GetLength (0) > 1)
				{
					datei_n = Convert.ToInt32 (zeile.Split (' ')[1]);
					datei_m = Convert.ToInt32 (zeile.Split (' ')[3]);
				}
				else
					return false;			// Basiswerte standen nicht in erster Zeile
				
				// Knoten einlesen
				for(int i=0; i< datei_n; i++)
				{
					zeile = reader.ReadLine ();
					if (zeile.Split (' ').GetLength (0) > 3)
					{
						int id = Convert.ToInt32 (zeile.Split (' ')[1]);
						int x = Convert.ToInt32 (zeile.Split (' ')[2]);
						int y = Convert.ToInt32 (zeile.Split (' ')[3]);
						neuerKnoten( new Knoten(id, x, y));
					}
				}
				
				// Kanten einlesen
				for(int i=0; i<datei_m; i++)
				{
					zeile = reader.ReadLine ();
					if (zeile.Split (' ').GetLength (0) > 2)
					{
						int von = Convert.ToInt32 (zeile.Split (' ')[1]);
						int nach = Convert.ToInt32 (zeile.Split (' ')[2]);
						
						// euklidische DIstanz bestimmen
						Knoten vvon = v[von];
						Knoten vnach = v[nach];
						// Manhatten-Distanz
						double gewicht = Math.Abs(vvon.x - vnach.x)
							+ Math.Abs(vvon.y - vnach.y);
						
						// euklidische Distanz
						/*	double gewicht = Math.Sqrt(
						   	Math.Pow((((DijkstraKnoten)vvon).x-((DijkstraKnoten)vnach).x),2) 
						  + Math.Pow((((DijkstraKnoten)vvon).y-((DijkstraKnoten)vnach).y),2)); */
						
						neueKante(von, nach, gewicht);
					}
				}
				
				reader.Close ();
				//Console.WriteLine("Graph geladen");
				return true;
			}
			
			return false;
		}
		
		public virtual bool speicherGraph (string pfad)
		{
			try {
				// Datei einlesen
				StreamWriter writer = new StreamWriter (pfad);
				writer.WriteLine ("n " + v.Count + " m " + m);
				
				foreach (Knoten w in v)
					foreach (Kante k in a[w.id])
						writer.WriteLine ("e " + k.Von + " " + k.Nach);
				
				writer.Close ();
				Console.WriteLine ("Graph gespeichert");
				return true;
			} catch {
				return false;
			}
		}

		public int M {
			get { return this.m; }
		}
		public List<Knoten> V {
			get { return this.v; }
		}
		public Dictionary<int, List<Kante>> A {
			get { return this.a; }
		}
		public Dictionary<int, List<Kante>> Ar {
			get { return this.ar; }
		}
	}
}

